W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
The names of towns in Byteotia are unique sequences of exactly bits. There are towns in Byteotia, and thus, only sequences of bits do not correspond to any town.
Some pairs of towns are connected with roads. Specifically, two towns are directly linked by a road if and only if their names differ in a single bit. The roads do not cross outside of towns.
Byteasar intends to take a stroll - he intends to walk from the town to the town , taking the existing roads. Your task is to write a program that will determine if such a walk is possible.
In the first line of the standard input, there are two integers, and (, , , ), separated by a single space. These are the length of town names in bits and the the number of -bit sequences that do not correspond to any town, respectively. In the second line, there are two strings, separated by a single space, each consisting of characters 0 and/or 1. These are the names of the towns and . In the lines that follow, all the sequences of bits that do not correspond to any town are given, one sequence per line. Each such sequence is a string of characters 0 and/or 1. You may assume that and are not among those sequences.
In tests worth 25% of total points the additional condition holds.
Your program should print to the standard output the word TAK (Polish for yes) if walking from the town to the town is possible, and the word NIE (Polish for no) otherwise.
For the input data:
4 6 0000 1011 0110 0111 0011 1101 1010 1001
the correct result is:
TAK
For the input data:
2 2 00 11 01 10
the correct result is:
NIE
Explanation of the first example: The following are two examples of a walk from 0000 to 1011:
Sample grading tests:
Task author: Wojciech Rytter
<Submit a solution> [0/100]